import java.util.Arrays;
import java.util.Comparator;

public class CountingSort {

    private Comparator<Integer> comparator;

    public CountingSort(Comparator<Integer> comparator) {
        this.comparator = comparator;
    }

    public void sort(Integer[] array) {

        /* 最小值 */
        Integer min = array[0];
        /* 最大值*/
        Integer max = array[0];

        for (Integer val : array) {
            if (val < min) {
                min = val;
            } else if (val > max) {
                max = val;
            }
        }

        int[] counts = new int[max - min + 1];

        for (Integer val : array) {
            int offset = val - min;
            ++counts[offset];
        }

        for (int i = 0, offset = 0; offset < counts.length; offset++) {
            int count = counts[offset];
            if (count <= 0) {
                continue;
            }

            Arrays.fill(array, i, i += count, offset + min);
        }

    }
}
